package _0_6_回文子串_子序列_编辑距离

/**
原题链接:
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

718. 最长重复子数组
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

思路:
一. dp数组含义
	dp[i][j]: 以i-1为结尾的nums1数组, 和以j-1为结尾的nums2的最长重复子序列

二. 递推公式
	if (nums1[i-1] == nums2[j-1]){   //如果当前位置元素相同,那么长度计数+1, 两者向前推进一个位置, 继续比较
		dp[i][j] = dp[i-1][j-1] + 1
	}

三. 初始化
	由于dp[i][0] dp[0][j]在题意下是没有意义的, 应该初始化为0.  无论两者谁长度为0,都会导致公共子序列的长度为0
	其它位置初始化为多少都可以, 因为会被覆盖, 就用默认的0即可

四. 遍历顺序
	先遍历nums1和nums2都是可以的.  因为求得是两者公共最长子序列
	for (i=1; i<=nums.size; i++){
		for (j=1; j<=nums2.size; j++) {
			if (nums1[i-1] == nums2[j-1]){   //如果当前位置元素相同,那么长度计数+1, 两者向前推进一个位置, 继续比较
				dp[i][j] = dp[i-1][j-1] + 1
			}

			if (dp[i][j] > result) {
				result = dp[i][j]
			}
		}
	}

	需要遍历二维数组中的每个元素, 找出最长的公共重复子数组

五. 打印dp数组
*/
// 分割等和子集 动态规划
// 时间复杂度O(n^2) 空间复杂度O(n)
func findLength(text1 []int, text2 []int) int {

	m, n := len(text1), len(text2) //分别获取A,B两个数组的长度
	res := 0                       //声明结果

	dp := make([][]int, m+1) //声明二维数组
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}

	for i := 1; i <= m; i++ { //填充数组
		for j := 1; j <= n; j++ {
			if text1[i-1] == text2[j-1] { //如果当前 数组A的i-1元素和数组B的j-1元素相等,那么重复子序列长度+1, 并进行递推
				dp[i][j] = dp[i-1][j-1] + 1
			}

			if dp[i][j] > res { //更新结果值
				res = dp[i][j]
			}
		}
	}

	return res //返回res结果
}
